An important business goal for any software company is to build a software product within a desired time frame and within a desired budget. To compete effectively in the marketplace, the software product also has to have quality. A software product that has quality has a number of desirable software properties, such as making appropriate use of computer resources.
The process of checking for these software properties is made up of problems for which there is not a solution comprising a step-by-step procedure that can be implemented in a computer. Software scientists couch these problems as undecidable problems. However, for certain software properties that are determinable, it is possible in some cases to confirm or deny the existence of these software properties. But such a process of analyzing is nontrivial.
One reason that such a process of analyzing is nontrivial is because a software product is produced from a program that may have several statements. These statements may include several variables. Additionally, these statements often are organized into several procedures. The need to consider the prohibitively large combinations of statements, variables, and procedures would cripple the process of analysis.
Current analysis techniques provide inferior information to check for software properties. These techniques typically suffer from an explosion in the amount of information to be analyzed. As the size of programs has increased with each generation of technology, such inferior information may slow the improvement of programs and lead to the eventual lack of acceptance of such programs in the marketplace, thus, what is needed are systems and methods to enhance program analysis.
Tools called Model checkers have been built to check properties of hardware and protocol designs, but they do not directly work on software programs. In particular, existing model checkers do not exploit procedural abstraction that is characteristic of imperative programs. An algorithm proposed by Reps/Horwitz/Sagiv (RHS) has been used to perform interprocedural flow-sensitive analysis by use of an exploded graph representation of a program. The algorithm is applicable to interprocedural, finite, distributive, subset problems having a finite set D of dataflow facts and distributive dataflow functions. The RHS algorithm does not handle arbitrary dataflow functions. Further, if the number of dataflow facts is very large, the explicit supergraph structure built by the RHS algorithm can be prohibitively expensive to build. It is desirable to change the RUS algorithm to both handle arbitrary dataflow functions and represent parts of the supergraph implicitly, as done in symbolic model checking algorithms.